from typing import List


class Solution:
    def dfs(self, board: List[List[str]], i: int, j: int):
        if i < 0:
            return
        if i >= len(board):
            return
        if j < 0:
            return
        if j >= len(board[0]):
            return
        if board[i][j] == "O":
            board[i][j] = "#"
            self.dfs(board, i, j - 1)
            self.dfs(board, i, j + 1)
            self.dfs(board, i - 1, j)
            self.dfs(board, i + 1, j)
        pass

    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return

        row = len(board)
        col = len(board[0])
        for r in range(row):
            self.dfs(board, r, 0)
            self.dfs(board, r, col - 1)
        for c in range(col):
            self.dfs(board, 0, c)
            self.dfs(board, row - 1, c)

        for r in range(row):
            for c in range(col):
                if board[r][c] == "O":
                    board[r][c] = "X"

        for r in range(row):
            for c in range(col):
                if board[r][c] == "#":
                    board[r][c] = "O"
